/*Fermat law
  If p is prime, then for all integers a, a ^ p (mod p) = a (mod p).
 */#include<stdio.h>
#include<math.h>
int main(){
	int p,k,i;
	bool flag;
	while(true){
		flag=true;
		scanf("%d",&p);
		k=sqrt(p);
		for(i=2;i<=k;i++)
			if(p%i==0)break;
		//is a prime or not
		if(i>k){
			for(int a=0;a<10;a++)
				if(((long long int)pow(a,p)-a)%p!=0){
					flag=false;
					a=10;
				}
			printf("%s\n",flag==true?"true":"false");
			/*
			  <=13的素数都正确，但10^17>long long的长度，
			  若要验证更大的数，则要运算符重载，偷了个懒^_^。
			*/
		}
		else printf("not a prime\n");
	}
	return 0;
}
